package letcode.oneQuestionPerDay._202004._26;

import letcode.util.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Description: 合并k个排序链表
 * @Date: 2020/4/26
 * @Author: 许群星
 */
public class MergeKLinkedList_a {
    public static void main(String[] args) {
        ListNode[] lists = new ListNode[3];
        ListNode first = new ListNode(1);
        first.next = new ListNode(3);
        first.next.next = new ListNode(4);

        ListNode second = new ListNode(1);
        second.next = new ListNode(4);
        second.next.next = new ListNode(5);

        ListNode third = new ListNode(2);
        third.next = new ListNode(6);

        lists[0] = second;
        lists[1] = first;
        lists[2] = third;

        ListNode head = mergeKLists(lists);
        System.out.println(head.val);
        System.out.println(head.next.val);
        System.out.println(head.next.next.val);
        System.out.println(head.next.next.next.val);
        System.out.println(head.next.next.next.next.val);
        System.out.println(head.next.next.next.next.next.val);
        System.out.println(head.next.next.next.next.next.next.val);
        System.out.println(head.next.next.next.next.next.next.next.val);
    }

    //提供方法         堆排优化：售票窗口
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        //创建小根堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return (o1.val - o2.val);
            }
        });
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        //只把k个链表的第一个节点放入到堆中
        for (int i = 0; i < lists.length; i++) {
            ListNode head = lists[i];
            if (head != null) {
                queue.add(head);
            }
        }
        //从堆冲取出节点，如果还有下一个节点的话，就将下一个节点放入到堆中
        while (queue.size() > 0) {
            ListNode node = queue.poll();
            curr.next = node;
            curr = curr.next;
            if (node.next != null) {
                queue.add(node.next);
            }
        }
        curr.next = null;
        return dummy.next;
    }

}
/*
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */